{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Substrings That Begin and End With the Same Letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #counting #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #计数 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求以相同字母开头和结尾的子串总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由小写英文字母组成的，&nbsp; 下标从 <code>0</code> 开始的字符串 <code>s</code> 。返回 <code>s</code> 中以相同字符开头和结尾的子字符串总数。</p>\n",
    "\n",
    "<p>子字符串是字符串中连续的非空字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcba\"\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "以相同字母开头和结尾的长度为 1 的子串是：\"a\"、\"b\"、\"c\"、\"b\" 和 \"a\" 。\n",
    "以相同字母开头和结尾的长度为 3 的子串是：\"bcb\" 。\n",
    "以相同字母开头和结尾的长度为 5 的子串是：\"abcba\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abacad\"\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>\n",
    "以相同字母开头和结尾的长度为 1 的子串是：\"a\"、\"b\"、\"a\"、\"c\"、\"a\" 和 \"d\" 。\n",
    "以相同字母开头和结尾的长度为 3 的子串是：\"aba\" 和 \"aca\" 。\n",
    "以相同字母开头和结尾的长度为 5 的子串是：\"abaca\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "只有一个，以相同字母开头和结尾的长度为 1 的子串是：\"a\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [substrings-that-begin-and-end-with-the-same-letter](https://leetcode.cn/problems/substrings-that-begin-and-end-with-the-same-letter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [substrings-that-begin-and-end-with-the-same-letter](https://leetcode.cn/problems/substrings-that-begin-and-end-with-the-same-letter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcba\"', '\"abacad\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        cnt = {}\n",
    "        \n",
    "        for r in range(n):\n",
    "            cnt[s[r]] = cnt.get(s[r], 0) + 1\n",
    "            if len(cnt) == 3:\n",
    "                ans += n -r\n",
    "            while len(cnt) == 3:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0: del cnt[s[l]]\n",
    "                l += 1\n",
    "                if len(cnt) == 3:\n",
    "                    ans += n - r\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans, left, right = 0, 0, -1\n",
    "        n = len(s)\n",
    "        cnt = {'a': 0, 'b': 0, 'c': 0}\n",
    "        while left < n:\n",
    "            while not all(cnt.values()):\n",
    "                right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                cnt[s[right]] += 1\n",
    "            if right == n:\n",
    "                break\n",
    "            ans += n - right\n",
    "            cnt[s[left]] -= 1\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        w=[0]*3\n",
    "        l=0 \n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            w[ord(s[i])-ord('a')]+=1\n",
    "            while l<=i and w[0]>0 and w[1]>0 and w[2]>0:\n",
    "                w[ord(s[l])-ord('a')]-=1\n",
    "                l+=1\n",
    "            if l>0:\n",
    "                res+=l \n",
    "        return res  \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, left = 0,0\n",
    "        cnt = Counter()\n",
    "        for right, c in enumerate(s):\n",
    "            cnt[c] += 1\n",
    "            while all(cnt[x]>0 for x in \"abc\"):\n",
    "                ans += (n-right)\n",
    "                cnt[s[left]] -=1\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "\n",
    "        if len(s) < 3:\n",
    "            return 0\n",
    "\n",
    "        cnt = Counter()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "\n",
    "            while cnt['a'] != 0 and cnt['b'] != 0 and cnt['c'] != 0:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "                ans += n - right\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans, left, right = 0, 0, -1\n",
    "        n = len(s)\n",
    "        cnt = Counter()\n",
    "        while left < n:\n",
    "            while len(cnt) < 3:\n",
    "                right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                cnt[s[right]] += 1\n",
    "            if right == n:\n",
    "                break\n",
    "            ans += n - right\n",
    "            cnt[s[left]] -= 1\n",
    "            if not cnt[s[left]]:\n",
    "                del cnt[s[left]]\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "\n",
    "        if len(s) < 3:\n",
    "            return 0\n",
    "\n",
    "        cnt = Counter()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "\n",
    "            while cnt['a'] != 0 and cnt['b'] != 0 and cnt['c'] != 0:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "                ans += n - right\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        count = [0]*3\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(s)):\n",
    "            count[ord(s[right]) - ord('a')] += 1\n",
    "            while count[0] > 0 and count[1] > 0 and count[2] > 0:\n",
    "                res += len(s) - right\n",
    "                count[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        la = lb = lc = -1\n",
    "        res = 0\n",
    "        for i, a in enumerate(s):\n",
    "            if a == 'a':\n",
    "                la = i\n",
    "            if a == 'b':\n",
    "                lb = i\n",
    "            if a == 'c':\n",
    "                lc = i\n",
    "            p = min(la, lb, lc)\n",
    "            res += p + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "    \t\t\t\tn = len(s)\n",
    "    \t\t\t\tans = left = 0\n",
    "    \t\t\t\tcnt = [0] * 3\n",
    "    \t\t\t\tfor right, x in enumerate(s):\n",
    "    \t\t\t\t    cnt[ord(x) - ord('a')] += 1\n",
    "    \t\t\t\t    while all(x > 0 for x in cnt) :\n",
    "    \t\t\t\t        ans += n - right\n",
    "    \t\t\t\t        cnt[ord(s[left]) - ord('a')] -= 1\n",
    "    \t\t\t\t        left += 1\n",
    "    \t\t\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        window = collections.defaultdict(int)\n",
    "        while right < len(s):\n",
    "            window[s[right]] += 1\n",
    "            while len(window) == 3:\n",
    "                res += len(s) - right\n",
    "                window[s[left]] -= 1\n",
    "                if window[s[left]] == 0:\n",
    "                    window.pop(s[left])\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        winfreq = {'a': 0, 'b': 0, 'c': 0}\n",
    "        count = 0\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            if winfreq[s[right]] == 0:\n",
    "                count += 1\n",
    "            winfreq[s[right]] += 1\n",
    "            \n",
    "            while count == 3:\n",
    "                res += n - right\n",
    "                winfreq[s[left]] -= 1\n",
    "                if winfreq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        if len(s) < 3: return 0\n",
    "\n",
    "        head, tail = 0, 2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        while head < n - 2:\n",
    "            tmp = s[head: tail + 1]\n",
    "            if 'a' in tmp and 'b' in tmp and 'c' in tmp:\n",
    "                ans += n - tail\n",
    "                head += 1\n",
    "            else:\n",
    "                tail += 1\n",
    "                if tail == n: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 2\n",
    "        cnt = 0\n",
    "        count_map = {'a':0,'b':0,'c':0}\n",
    "        # check if the s[l], s[l+1], ..., s[r] is valid\n",
    "        # l, l+1, ..., r, r+1, ..., n-1=r+(n-1-r)\n",
    "        # if it is valid: cnt+=(n-1-r), and l+=1\n",
    "        for i in range(3):\n",
    "            count_map[s[i]]+=1\n",
    "\n",
    "        while l <= n-3 and r < n:\n",
    "            if count_map['a'] > 0 and count_map['b'] > 0 and count_map['c'] > 0:\n",
    "                cnt+=1+(n-1-r)  # need to count the current one\n",
    "                count_map[s[l]]-=1\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "                if r < len(s):\n",
    "                    count_map[s[r]]+=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans, left, right = 0, 0, -1\n",
    "        n = len(s)\n",
    "        cnt = {}\n",
    "        while left < n:\n",
    "            while len(cnt) < 3:\n",
    "                right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "                cnt[s[right]] = cnt.get(s[right], 0) + 1\n",
    "            if right == n:\n",
    "                break\n",
    "            ans += n - right\n",
    "            cnt[s[left]] -= 1\n",
    "            if not cnt[s[left]]:\n",
    "                del cnt[s[left]]\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        p0 = 0\n",
    "        count = defaultdict(int)\n",
    "        for p1 in range(len(s)):\n",
    "            count[s[p1]] += 1\n",
    "            while True:\n",
    "                if count['a'] > 0 and count['b'] > 0 and count['c'] > 0:\n",
    "                    ans += len(s) - p1\n",
    "                    count[s[p0]] -= 1\n",
    "                    p0 += 1\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        record = 2\n",
    "        for i in range(len(s)-2):\n",
    "            for j in range(record,len(s)):\n",
    "                if 'a' in s[i:j+1] and 'b' in s[i:j+1] and 'c' in s[i:j+1]:\n",
    "                    cnt+=len(s)-j\n",
    "                    record = j\n",
    "                    break\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        l=0\n",
    "        r=2\n",
    "        #对每一个起始位置i来说，s[i:j+1]为最少的包含abc的串，则数量为l-(j-i+1)+1 = l-j+i\n",
    "        while l<len(s)-2:\n",
    "            tmp = s[l:r+1]\n",
    "            if 'a' in tmp and 'b' in tmp and 'c' in tmp:\n",
    "                res += len(s)-r\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "                if r == len(s):\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        a,b,c = 0,0,0\n",
    "        start = 0\n",
    "\n",
    "        for end in range(len(s)):\n",
    "            if s[end]=='a':\n",
    "                a += 1\n",
    "            elif s[end]=='b':\n",
    "                b += 1\n",
    "            else:\n",
    "                c += 1\n",
    "            while a>=1 and b>=1 and c>=1:\n",
    "                res += len(s)-end \n",
    "                if s[start]=='a':\n",
    "                    a-=1\n",
    "                elif s[start]=='b':\n",
    "                    b-=1\n",
    "                else:\n",
    "                    c-=1\n",
    "                start += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(1)\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        getNum = {\"a\": 0, \"b\": 1, \"c\": 2} \n",
    "        window = [0, 0, 0]\n",
    "        while r < n:\n",
    "            window[getNum[s[r]]] += 1\n",
    "            while min(window) > 0:\n",
    "                window[getNum[s[l]]] -= 1\n",
    "                l += 1\n",
    "            # now [0, r], ..., [l-1,r] all have at least 1 occurrence of all 3 chars\n",
    "            # there are (l - 1) - 0 + 1 = l substrings\n",
    "            res += l\n",
    "            r += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cc=Counter()\n",
    "        l=0\n",
    "        n=len(s)\n",
    "        res=0\n",
    "        for r,c in enumerate(s):\n",
    "            cc[c]+=1\n",
    "            while cc['a'] and cc['b'] and cc['c']:\n",
    "                cc[s[l]]-=1\n",
    "                l+=1\n",
    "            res+=(r-l+1)\n",
    "        return n*(n+1)//2 -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0, 0, 0]\n",
    "        left = 0\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while all(cnt):\n",
    "                cnt[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            # 子串越长越符合要求\n",
    "            # 当 right 固定时，满足要求的子数组有：\n",
    "            # [0, right]\n",
    "            # [1, right]\n",
    "            # ...\n",
    "            # [left-1, right]\n",
    "            # 一共是 left 个\n",
    "            ans += left\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        aidx, bidx, cidx = None, None, None\n",
    "        result = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if(c == 'a'):\n",
    "                if(bidx != None and cidx != None):\n",
    "                    result += min(bidx, cidx) + 1\n",
    "                aidx = i\n",
    "            if(c == 'b'):\n",
    "                if(aidx != None and cidx != None):\n",
    "                    result += min(aidx, cidx) + 1\n",
    "                bidx = i\n",
    "            if(c == 'c'):\n",
    "                if(aidx != None and bidx != None):\n",
    "                    result += min(aidx, bidx) + 1\n",
    "                cidx = i \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, res = 0, 0\n",
    "        d = Counter(['a', 'b', 'c'])\n",
    "        d_s = Counter()\n",
    "        for r, c in enumerate(s):\n",
    "            d_s[c] += 1\n",
    "            while d_s >= d:\n",
    "                res += n - r\n",
    "                d_s[s[l]] -= 1\n",
    "                l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        left, ans, cnt = 0, 0, defaultdict(int)\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) >= 3:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            ans += left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        temp = [0] * 3\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            temp[ord(s[right]) - ord('a')] += 1\n",
    "            if min(temp) >= 1:\n",
    "                ans += len(s) - right\n",
    "                while True:\n",
    "                    temp[ord(s[left]) - ord('a')] -= 1\n",
    "                    left += 1\n",
    "                    if min(temp) >= 1:\n",
    "                        ans += len(s) - right\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        if len(s) < 3:\n",
    "            return 0\n",
    "        left, right = 0, 2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        while left < n - 2:\n",
    "            tmp = s[left: right + 1]\n",
    "            if 'a' in tmp and 'b' in tmp and 'c' in tmp:\n",
    "                ans += n - right\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "                if right == n:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        window = dict()\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "\n",
    "        while right < n:\n",
    "            window[s[right]] = window.get(s[right], 0) + 1\n",
    "            while len(window) == 3:\n",
    "                window[s[left]] -= 1\n",
    "                if window[s[left]] == 0:\n",
    "                    del window[s[left]]\n",
    "                left += 1\n",
    "            right += 1\n",
    "            ans += left\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        right_a = -1\n",
    "        right_b = -1\n",
    "        right_c = -1\n",
    "        for idx,cur in enumerate(s):\n",
    "            if cur == 'a':\n",
    "                right_a = idx\n",
    "            if cur == 'b':\n",
    "                right_b = idx\n",
    "            if cur == 'c':\n",
    "                right_c = idx\n",
    "            left = min(right_a,right_b,right_c)\n",
    "            if left > -1:             \n",
    "                res += left + 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left,right=0, 0\n",
    "        count=0 #出现的字符种数\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            freq[c] = 0\n",
    "        res=0\n",
    "        while right < n:\n",
    "            freq[s[right]] += 1\n",
    "            if freq[s[right]] == 1:\n",
    "                count += 1\n",
    "            \n",
    "            while count == 3:\n",
    "                res += n-right\n",
    "                freq[s[left]] -= 1\n",
    "                if freq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                \n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfSubstrings(self, s: str) -> int:\r\n",
    "\r\n",
    "        required = {'a' : 0, 'b' : 0, 'c' : 0}\r\n",
    "        n = len(s)\r\n",
    "        if n < 3:\r\n",
    "            return 0\r\n",
    "        ans = 0\r\n",
    "        left = right = 0\r\n",
    "        first_valid = 0\r\n",
    "        if s[right] in required:\r\n",
    "            required[s[right]] += 1\r\n",
    "        while left <= right and right < n:\r\n",
    "            valid = True\r\n",
    "            \r\n",
    "            for key, value in required.items():\r\n",
    "                if value == 0:\r\n",
    "                    valid = False\r\n",
    "                    break\r\n",
    "\r\n",
    "            if valid == True:\r\n",
    "                ans += n - right\r\n",
    "                if s[left] in required:\r\n",
    "                    required[s[left]] -= 1\r\n",
    "                left += 1\r\n",
    "            else:\r\n",
    "                right += 1\r\n",
    "                if right < n and s[right] in required:\r\n",
    "                    required[s[right]] += 1\r\n",
    "        return ans\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        window = {c: 0 for c in \"abc\"}\n",
    "\n",
    "        left = 0\n",
    "        res = 0\n",
    "        # 遍历右边界\n",
    "        for right, c in enumerate(s):\n",
    "            window[c] += 1\n",
    "\n",
    "            # 判断此时窗口内是否都出现过1次abc\n",
    "            # 如果是的话，则缩减左边界\n",
    "            while all(v >= 1 for v in window.values()) and left < right:\n",
    "                d = s[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "            res = res + left\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # i = 0\n",
    "        \n",
    "        # res = 0\n",
    "        # while i < n:\n",
    "        #     j = i + 2\n",
    "        #     while j < n:\n",
    "                \n",
    "        #         lst = list(s)[i : j+1]\n",
    "                \n",
    "        #         cnt = Counter(lst)\n",
    "        #         if cnt['a'] >= 1 and cnt['b'] >= 1 and cnt['c'] >= 1:\n",
    "        #             res += 1\n",
    "        #         j += 1\n",
    "                \n",
    "        #     i += 1\n",
    "        # return res\n",
    "        n = len(s)\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        cnt_c = 0\n",
    "\n",
    "        res = 0\n",
    "        L = 0\n",
    "        for R in range(n):\n",
    "            if s[R] == 'a':     cnt_a += 1\n",
    "            if s[R] == 'b':     cnt_b += 1\n",
    "            if s[R] == 'c':     cnt_c += 1\n",
    "\n",
    "            while cnt_a >= 1 and cnt_b >= 1 and cnt_c >= 1:\n",
    "                res += (n - R)                  #与右侧剩下的，可以组成合法的情况（R也是合理的）\n",
    "\n",
    "                if s[L] == 'a':     cnt_a -= 1\n",
    "                if s[L] == 'b':     cnt_b -= 1\n",
    "                if s[L] == 'c':     cnt_c -= 1\n",
    "                L += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        # a aacb\n",
    "        # aaacb aacb acb\n",
    "        # 当i在某个位置，找到第一个符合条件的j，后面的都符合条件\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        cnt = [0] * 3\n",
    "        l,r = 0,0\n",
    "        while l<n:\n",
    "            while r<n and not (cnt[0] >=1 and cnt[1] >=1 and cnt[2] >= 1):\n",
    "                cnt[ord(s[r]) - ord('a')] +=1\n",
    "                r+=1\n",
    "            if cnt[0] >=1 and cnt[1] >=1 and cnt[2] >= 1:\n",
    "                res += n - r + 1\n",
    "            cnt[ord(s[l]) - ord('a')] -=1\n",
    "            l+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l = 0\n",
    "        count = 0\n",
    "        counter = Counter()\n",
    "\n",
    "        for r in range(n):\n",
    "            counter[s[r]] += 1\n",
    "            while len(counter) == 3:\n",
    "                count += n - r\n",
    "                counter[s[l]] -= 1\n",
    "                if counter[s[l]] == 0:\n",
    "                    del counter[s[l]]\n",
    "                l += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        counter = {'a':0, 'b':0, 'c':0}\n",
    "        n = len(s)\n",
    "        lp = rp = 0\n",
    "\n",
    "        while rp < n:\n",
    "            counter[s[rp]] += 1\n",
    "            while all(i>0 for i in counter.values()):\n",
    "                res += n - rp\n",
    "                counter[s[lp]] -= 1\n",
    "                lp += 1\n",
    "            rp += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt = {'a': 0, 'b': 0, 'c': 0}\n",
    "        ans, r = 0, -1\n",
    "        len_s = len(s)\n",
    "\n",
    "        for l in range(len_s):\n",
    "            while r < len_s and not all(cnt[c] >= 1 for c in \"abc\"):\n",
    "                r += 1\n",
    "                if r == len_s:\n",
    "                    break\n",
    "                cnt[s[r]] += 1\n",
    "            ans += len_s - r\n",
    "            cnt[s[l]] -= 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        dp = [ 0 for _ in range(3) ]\n",
    "        dic = { \"a\": 0, \"b\": 1, \"c\": 2 }\n",
    "        left = right = 0\n",
    "        ans = 0\n",
    "        N = len(s)\n",
    "        while right <= len(s) - 1:\n",
    "            dp[dic[s[right]]] += 1\n",
    "            while left <= right and dp[0] and dp[1] and dp[2]:\n",
    "                ans += N - right\n",
    "                dp[dic[s[left]]] -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        # abcabc\n",
    "        # 当 l = 0, r = 2 时，子串就是 abc，那么此时r右侧全部都满足\n",
    "        # 一共有4个\n",
    "        right = 0\n",
    "        window = {c: 0 for c in \"abc\"}\n",
    "        cnt = 0\n",
    "        num_s = len(s)\n",
    "\n",
    "        for left, d in enumerate(s):\n",
    "            while right < len(s) and any(v == 0 for v in window.values()):\n",
    "                c = s[right]\n",
    "                window[c] += 1\n",
    "                right += 1\n",
    "            # 满足全部至少有1个\n",
    "            if all(v >= 1 for v in window.values()):\n",
    "                cnt += len(s) - right + 1\n",
    "            window[d] -= 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "\n",
    "        if len(s) < 3:\n",
    "            return 0\n",
    "\n",
    "        cnt = Counter()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "\n",
    "            while cnt['a'] != 0 and cnt['b'] != 0 and cnt['c'] != 0:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "                ans += n - right\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt = [0] * 3\n",
    "        i = j = 0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            while min(cnt) == 0 and i < n:\n",
    "                cnt[ord(s[i]) - ord('a')] += 1\n",
    "                i += 1\n",
    "            while min(cnt) != 0:\n",
    "                ans += n - i + 1\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        index = [0] * 3\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s, 1):\n",
    "            index[ord(c) - 97] = i\n",
    "            ans += min(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        counts = {'a': 0, 'b': 0, 'c': 0}\n",
    "        r, res = 0, 0\n",
    "        for l in range(len(s)):\n",
    "            while (counts['a'] == 0 or counts['b'] == 0 or counts['c'] == 0) and r < len(s):\n",
    "                counts[s[r]] += 1\n",
    "                r += 1\n",
    "            if counts['a'] and counts['b'] and counts['c']:\n",
    "                res += (len(s) - r + 1)\n",
    "            counts[s[l]] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "     g = defaultdict(int)\n",
    "     length = len(s)\n",
    "     l = 0\n",
    "     ans = 0\n",
    "     for i in range(length):\n",
    "        g[ord(s[i]) - ord('a')] += 1\n",
    "        while g[0] > 0 and g[1] > 0 and g[2] > 0:\n",
    "            ans += length - i\n",
    "            g[ord(s[l]) - ord('a')] -= 1\n",
    "            l += 1\n",
    "     return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt_ch={'a':0,'b':0,'c':0}\n",
    "        cnt=0\n",
    "        for i in range(len(s)):\n",
    "            cnt_ch[s[i]]=i+1\n",
    "            cnt+=min(cnt_ch['a'],cnt_ch['b'],cnt_ch['c'])   \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        res = 0\n",
    "        record = {'a': 0, 'b': 0, 'c': 0}\n",
    "        while right < n and (record['a'] == 0 or record['b'] == 0 or record['c'] == 0):\n",
    "            record[s[right]] += 1\n",
    "            right += 1\n",
    "        if right == n:\n",
    "            if record['a'] == 0 or record['b'] == 0 or record['c'] == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                res += n - right + 1\n",
    "        \n",
    "        res = n - right + 1\n",
    "        while right <= n:\n",
    "            ch = s[left]\n",
    "            record[ch] -= 1\n",
    "            left += 1\n",
    "            if record[ch] > 0:\n",
    "                res += n - right + 1\n",
    "            else:\n",
    "                while right < n and s[right] != ch:\n",
    "                    record[s[right]] += 1\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    return res\n",
    "                record[s[right]] += 1\n",
    "                right += 1\n",
    "                res += n - right + 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        record = defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            record[s[right]] += 1\n",
    "\n",
    "            while left <= right and left < len(s) and len(record) == 3:\n",
    "                res += len(s) - right\n",
    "\n",
    "                record[s[left]] -= 1\n",
    "                if record[s[left]] == 0:\n",
    "                    record.pop(s[left])\n",
    "\n",
    "                left += 1\n",
    "\n",
    "            right += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "\n",
    "        # 利用滑动窗口寻找至少存在abc一次的最短字符串[slow, fast]\n",
    "        # 以slow为开头，结尾从fast 到 (len(s)-1) 由于[slow, fast]至少包含abc，因此后续的都可以\n",
    "        # 只要slow发生变动，对于新的[slow, fast]，其个数为len(s) - fast \n",
    "        slow, fast = 0, 0\n",
    "        res = 0\n",
    "        d = {}\n",
    "        distance = 0\n",
    "        while fast < len(s):\n",
    "            if s[fast] in d:\n",
    "                d[s[fast]] += 1\n",
    "            else:\n",
    "                d[s[fast]] = 1\n",
    "                distance += 1\n",
    "            while distance >= 3:\n",
    "                d[s[slow]] -= 1\n",
    "                if d[s[slow]] == 0:\n",
    "                    del d[s[slow]]\n",
    "                    distance -= 1\n",
    "                slow += 1\n",
    "                res += len(s) - fast\n",
    "            fast += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt = {'a': 0, 'b': 0, 'c': 0}\n",
    "        ans, r = 0, -1\n",
    "        len_s = len(s)\n",
    "\n",
    "        for l in range(len_s):\n",
    "            while r < len_s and not all(cnt[c] >= 1 for c in \"abc\"):\n",
    "                r += 1\n",
    "                if r == len_s:\n",
    "                    break\n",
    "                cnt[s[r]] += 1\n",
    "            ans += len_s - r\n",
    "            cnt[s[l]] -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        collection = dict()\n",
    "\n",
    "        slow = 0\n",
    "        fast =0\n",
    "        ans =0\n",
    "\n",
    "        while fast < len(s):\n",
    "            if not s[fast] in collection:\n",
    "                collection[s[fast]] =1\n",
    "            else:\n",
    "                collection[s[fast]] +=1\n",
    "            \n",
    "            while len(collection)>=3:\n",
    "                ans += len(s) - fast\n",
    "                collection[s[slow]] -= 1\n",
    "                if collection[s[slow]] == 0:\n",
    "                    del collection[s[slow]]\n",
    "                slow += 1\n",
    "\n",
    "            fast +=1    \n",
    "\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        index = {'a': -1, 'b': -1, 'c': -1}\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            index[s[i]] = i\n",
    "            left = min(index.values())\n",
    "            if left >= 0: ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        index = [0] * 3\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s, 1):\n",
    "            index[ord(c) - 97] = i\n",
    "            ans += min(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        la = lb = lc = -1\n",
    "        res = 0\n",
    "        for i, a in enumerate(s):\n",
    "            if a == 'a':\n",
    "                la = i\n",
    "            if a == 'b':\n",
    "                lb = i\n",
    "            if a == 'c':\n",
    "                lc = i\n",
    "            p = min(la, lb, lc)\n",
    "            res += p + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        # 初始化一个数组来记录每个字符（'a', 'b', 'c'）最近一次出现的位置\n",
    "        index = [-1] * 3\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历字符串的每个字符\n",
    "        for i in range(n):\n",
    "            # 更新当前字符在 index 数组中的位置\n",
    "            index[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "            # 找到 index 数组中的最小值，即 'a', 'b', 'c' 最早出现位置的最大值\n",
    "            left = min(index)\n",
    "\n",
    "            # 如果 left >= 0，表示 'a', 'b', 'c' 都至少出现了一次\n",
    "            # 从字符串开头到位置 left 有 left + 1 个不同的有效子字符串\n",
    "            if left >= 0: \n",
    "                res += left + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        #'aabac' -> 3\n",
    "        #'' -> 0\n",
    "        #'b' -> 0\\\n",
    "        #bccbccccaaa\n",
    "        res = 0\n",
    "        import collections\n",
    "        count = {'a':0, 'b':0,'c':0}\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            count[s[right]] += 1\n",
    "            while min(count.values()) > 0:\n",
    "                #print(count, right, len(s) - right)\n",
    "                res += len(s) - right\n",
    "                count[s[left]] -= 1\n",
    "                left += 1           \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        freq = [0] * 3\n",
    "        uniq = 0\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for j, ch in enumerate(s):\n",
    "            o = ord(ch) - ord(\"a\")\n",
    "            freq[o] += 1\n",
    "            if freq[o] == 1:\n",
    "                uniq += 1\n",
    "            while uniq == 3:\n",
    "                ans += n - j\n",
    "                o = ord(s[i]) - ord(\"a\")\n",
    "                freq[o] -= 1\n",
    "                if freq[o] == 0:\n",
    "                    uniq -= 1\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ## 容斥\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        l = 0\n",
    "        cnt =defaultdict(int)\n",
    "        for r,c in enumerate(s):\n",
    "            cnt[c]+=1\n",
    "            while cnt['a'] and cnt['b'] and cnt['c']:\n",
    "                cnt[s[l]]-=1\n",
    "                l+=1\n",
    "            res += (r-l+1)\n",
    "        return (n+1)*n//2 -res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        result = 0\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        char_counter = defaultdict(int)\n",
    "        count = 0\n",
    "        while left < n:\n",
    "            while right < n and count < 3:\n",
    "                c = s[right]\n",
    "                if char_counter[c] == 0:\n",
    "                    count += 1\n",
    "                char_counter[c] += 1\n",
    "                right += 1\n",
    "            if count == 3:\n",
    "                result += n - right + 1\n",
    "            c = s[left]\n",
    "            if char_counter[c] == 1:\n",
    "                count -= 1\n",
    "            char_counter[c] -= 1\n",
    "            left += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return 0\n",
    "\n",
    "        i = 0\n",
    "        j = i+3\n",
    "        now = [0,0,0]\n",
    "        for z in range(0, 3):\n",
    "            now[ord(s[z])-97] +=1\n",
    "        \n",
    "        out = 0\n",
    "        while i < len(s)-2:\n",
    "            if 0 not in now:\n",
    "                out += (len(s)-j + 1)\n",
    "                now[ord(s[i])-97] -= 1\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "                if j > len(s):\n",
    "                    break\n",
    "                now[ord(s[j-1])-97] += 1\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def numberOfSubstrings(self, s: str) -> int:\n",
    "#         count = 0\n",
    "#         for i in range(len(s)):\n",
    "#             for j in range(i+1, len(s)+1):\n",
    "#                 substring = s[i:j]\n",
    "#                 if 'a' in substring and 'b' in substring and 'c' in substring:\n",
    "#                     count += 1\n",
    "#         return count\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        cnt_c = 0\n",
    "\n",
    "        res = 0\n",
    "        L = 0\n",
    "        for R in range(n):\n",
    "            if s[R] == 'a':     cnt_a += 1\n",
    "            if s[R] == 'b':     cnt_b += 1\n",
    "            if s[R] == 'c':     cnt_c += 1\n",
    "\n",
    "            while cnt_a >= 1 and cnt_b >= 1 and cnt_c >= 1:\n",
    "                res += (n - R)                  #与右侧剩下的，可以组成合法的情况（R也是合理的）\n",
    "\n",
    "                if s[L] == 'a':     cnt_a -= 1\n",
    "                if s[L] == 'b':     cnt_b -= 1\n",
    "                if s[L] == 'c':     cnt_c -= 1\n",
    "                L += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        index = [-1] * 3\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            index[ord(c) - 97] = i\n",
    "            left = min(index)\n",
    "            if left >= 0: \n",
    "                ans += left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, S: str) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0, 0, 0]\n",
    "        left = 0\n",
    "        s = list(S)\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while all(cnt):\n",
    "                cnt[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            # 子串越长越符合要求\n",
    "            # 当 right 固定时，满足要求的子数组有：\n",
    "            # [0, right]\n",
    "            # [1, right]\n",
    "            # ...\n",
    "            # [left-1, right]\n",
    "            # 一共是 left 个\n",
    "            ans += left\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        index = [0] * 3\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s, 1):\n",
    "            index[ord(c) - 97] = i\n",
    "            ans += min(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        na, nb, nc = -1, -1, -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                na = i\n",
    "            elif s[i] == 'b':\n",
    "                nb = i\n",
    "            else:\n",
    "                nc = i\n",
    "            ans = ans + min(na, nb, nc) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = {'a': 0, 'b': 0, 'c': 0}\n",
    "        n = len(s)\n",
    "        def helper(d):\n",
    "            return all(i > 0 for i in d.values())\n",
    "\n",
    "        for right in range(n):\n",
    "            dic[s[right]] += 1\n",
    "            while helper(dic):\n",
    "                dic[s[left]] -= 1\n",
    "                left += 1\n",
    "                res += n - right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = {'a': 0, 'b': 0, 'c': 0}\n",
    "        n = len(s)\n",
    "        def helper(d):\n",
    "            return all(i > 0 for i in d.values())\n",
    "\n",
    "        for right in range(n):\n",
    "            dic[s[right]] += 1\n",
    "            while helper(dic):\n",
    "                dic[s[left]] -= 1\n",
    "                left += 1\n",
    "                res += n - right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = {'a': 0, 'b': 0, 'c': 0}\n",
    "        n = len(s)\n",
    "        def helper(d):\n",
    "            return all(i > 0 for i in d.values())\n",
    "\n",
    "        for right in range(n):\n",
    "            dic[s[right]] += 1\n",
    "            while helper(dic):\n",
    "                dic[s[left]] -= 1\n",
    "                left += 1\n",
    "                res += n - right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return 0\n",
    "\n",
    "        i = 0\n",
    "        j = i+3\n",
    "        now = [0,0,0]\n",
    "        for z in range(0, 3):\n",
    "            now[ord(s[z])-97] +=1\n",
    "        \n",
    "        out = 0\n",
    "        while i < len(s)-2:\n",
    "            if 0 not in now:\n",
    "                out += (len(s)-j + 1)\n",
    "                now[ord(s[i])-97] -= 1\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "                if j > len(s):\n",
    "                    break\n",
    "                now[ord(s[j-1])-97] += 1\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnts, ans = [0] * 26, 0\n",
    "        for c in s:\n",
    "            cnts[ord(c) - ord('a')] += 1\n",
    "            ans += cnts[ord(c) - ord('a')]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(s):\n",
    "            prev = m1.get(v, 0)\n",
    "            if prev == 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt += 1 + prev\n",
    "            m1[v] += 1\n",
    "        return cnt\n",
    "\n",
    "a = Solution()\n",
    "print(a.numberOfSubstrings(\"abacad\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 遍历每个字母可以作为结尾的子串个数，实际上是前面该字符出现的次数。\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnts, ans = [0] * 26, 0\n",
    "        for c in s:\n",
    "            cnts[ord(c) - ord('a')] += 1\n",
    "            ans += cnts[ord(c) - ord('a')]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        counter = collections.Counter(s)\n",
    "        res = 0\n",
    "        for k, v in counter.items():\n",
    "            res += (v*(v+1)) // 2\n",
    "        return res\n",
    "        \n",
    "    def numberOfSubstrings2(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        pre = [0] * 26\n",
    "        for c in s:\n",
    "            pre[ord(c) - ord('a')] += 1\n",
    "            ans += pre[(ord(c) - ord('a'))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            ans += comb(v, 2) + v\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 遍历每个字母可以作为结尾的子串个数，实际上是前面该字符出现的次数。\n",
    "    def numberOfSubstrings1(self, s: str) -> int:\n",
    "        cnt, ans = [0] * 26, 0\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            ans += cnt[ord(c) - ord('a')]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 也可以直接统计所有次数，一起计算组合数。\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        return sum(v * (v + 1) >> 1 for v in Counter(s).values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        ans = len(s)\n",
    "        dic = defaultdict(int)\n",
    "        for x in s:\n",
    "            ans += dic[x]\n",
    "            dic[x] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt=Counter(s)\n",
    "        ans=0\n",
    "        for i in cnt.keys():\n",
    "            ans+=cnt[i]*(cnt[i]+1)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 遍历每个字母可以作为结尾的子串个数，实际上是前面该字符出现的次数。\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        cnt, ans = [0] * 26, 0\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            ans += cnt[ord(c) - ord('a')]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubstrings(self, s: str) -> int:\n",
    "        c = Counter(list(s))\n",
    "        return sum(c[a] * (c[a] - 1) // 2 for a in c) + len(s)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
